#include <iostream>
  #include <fstream>
  #include <assert.h>
  #include <malloc.h>
  #include <stdlib.h>
  #include <time.h>
  #include <stdio.h>
  #include <iomanip>
  #include <vector>
  #include <math.h>	
 #include "EA.h"
using namespace std;
//---------------------------------------------------------------------------
extern FILE *Stream;
extern char * GraphArq;
const int GROW = 100;
const int TRIES = 20;

//int inNode;
int inPopSize;
int inComSize;
int inCurrentForestName;
int inMaxPop;
int inMaxCom;
int inMaxColunm;
int inRestriction;
int inBestForest;
int inWorstForest;
double fpBestFitness;
double fpWorstFitness;
int inGeneration = 1;
int * same_operator;

GraphNode *stNodesAT;
GraphNode *tree1;
int inNumberNodesAT;

PositionMatrix *PI;
int inNumberNodesPI;
int inNumberNodespi;
int inFirstForest;
int *pi;

bool reloadPi;
//int nodeInit; //root
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
graph g;
int parent[MAXV];               /* discovery relation */

void initialize_graph (graph *g) {

	int i;				/* counter */

	g -> nvertices = 0;
	g -> nedges = 0;

	for (i=0; i<MAXV; i++) g->degree[i] = 0;
}


int read_graph(graph *g, char *filename, bool directed) 
{
  FILE* arq;
  int i;				/* counter */
  int m;				/* number of edges */
  int x,y;
  float w;			/* placeholder for edge and weight */

  initialize_graph(g);

  if((arq = fopen(filename, "rt")) == NULL)
    return 0;
  else {
    printf("read_graph abriu o arquivo \n");
    fscanf(arq, "%d\n",&(g->nvertices));
    while (!feof(arq)) {
      fscanf(arq, "%d %d %f\n",&x,&y,&w);
      insert_edge(g,x,y,directed,w);
    }
  }
  if( arq )
      fclose( arq );

  return 1;
}
	
void insert_edge(graph *g, int x, int y, bool directed, float w) {

	if (g->degree[x] > MAXDEGREE)
		printf("Warning: insertion(%d,%d) exceeds degree bound MAXDEGREE %d g.degree %d\n",x,y,MAXDEGREE,g->degree[x]);

	g->edges[x][g->degree[x]].v = y;
	g->edges[x][g->degree[x]].weight = w;
	/*g->edges[x][g->degree[x]].in = FALSE;*/
	g->degree[x] ++;

	if (directed == FALSE)
		insert_edge(g,y,x,TRUE,w);
	else
		g->nedges ++;
}


void delete_edge(graph *g, int x,int y,bool directed)
{
	int i;				/* counter */

	for (i=0; i<g->degree[x]; i++) 
		if (g->edges[x][i].v == y) {
			g->degree[x] --;
			g->edges[x][i] = g->edges[x][g->degree[x]];

			if (directed == FALSE)
				delete_edge(g,y,x,TRUE);

			return;
		}

	printf("Warning: deletion(%d,%d) not found in g.\n",x,y);
}

void print_graph(graph *g) /* graph to print */
{
	int i,j;			/* counters */

	for (i=0; i<g->nvertices; i++) {
		printf("%d: ",i);
		for (j=0; j<g->degree[i]; j++)
			printf(" %d",g->edges[i][j].v);
		printf("\n");
	}
}

bool processed[MAXV];		/* which vertices have been processed */
bool discovered[MAXV];          /* which vertices have been found */


void initialize_search(graph *g) /* graph to traverse */
{
        int i;                          /* counter */

        for (i=0; i<g->nvertices; i++) {
                processed[i] = FALSE;
                discovered[i] = FALSE;
                parent[i] = -1;
        }
}

//---------------------------------------------------------------------------

void CreateSpanningTree(graph *g, int start, int inRestrictionParam) {
	int i,j;			/* counters */
	bool intree[MAXV];		/* is the vertex in the tree yet? */
	float distance[MAXV];		/* distance vertex is from start */
	int stRestriction[MAXV];
	int v;				/* current vertex to process */
	int w;				/* candidate next vertex */
	float weight;			/* edge weight */
	float dist;			/* best current distance from start */
	
	//printf("n-vertices %d\n", g->nvertices);
	for (i=0; i<g->nvertices; i++) {
		intree[i] = FALSE;
		distance[i] = MAXINT;
		parent[i] = -1;
	}

	distance[start] = 0;
	v = start;
	while (intree[v] == FALSE) {
		intree[v] = TRUE;
		stRestriction[v] = 0;
		for (i=0; i<g->degree[v]; i++) {
			w = g->edges[v][i].v;
			weight = g->edges[v][i].weight;
			if ((distance[w] > weight) && (intree[w] == FALSE) && (stRestriction[v] < inRestrictionParam)) {
			        stRestriction[v]++;
				distance[w] = weight;
				parent[w] = v;
			}
			else if(stRestriction[v] > inRestrictionParam)
				i = g->degree[v];
		}

		v = 1;
		dist = MAXINT;
		for (i=0; i<g->nvertices; i++) 
			if ((intree[i] == FALSE) && (dist > distance[i])) {
				dist = distance[i];
				v = i;
			}
	}
}

// Tree *Prim(graph *g, int start, int inRestriction) {
// 	int i;
// 	int j;
// 	int inIndex;
// 	int inIndexInsert;
// 	int inIndexTree;
// 	int *stIndex;
// 	int *stNodes;
// 	Tree *stTree = Malloc(Tree, 1);
// 	
// 	CreateSpanningTree(g, start, inRestriction);
// 	
// 	stTree->stNodes = Malloc(int, g->nvertices+1);
// 	stTree->stDephs = Malloc(int, g->nvertices+1);
// 	stIndex = Malloc(int, 1);
// 	stTree->inNumberNodes = 0;
// 	stTree->inTreeName = 0;
// 	stNodes = Malloc(int, g->nvertices);
// 	for (i=0; i<= g->nvertices; i++) 
//         {  
// 	  stTree->stNodes[i] = -1;
// 	  stTree->stDephs[i] = 0;
// 	}
// 	for (i=0; i<g->nvertices; i++) {
// 	  /*printf(" %d parent=%d\n",i,parent[i]);*/
// 	  //Tree *stTree, int start, int end, int *deph, int *index, int*parents
// 	  for (j=0; j<g->nvertices; j++) {
// 	    stNodes[j] = -1;
// 	  }
//           stIndex[0] = 0;
// 	  find_path(stNodes, start, i, stIndex, parent);
// 	  
// 	  inIndex = 0;
// 	  inIndexTree = 0;
// 	  while (stNodes[inIndex] != -1 && inIndex < g->nvertices)
//           { // printf("inIndex %d inIndexTree %d \n",inIndex,inIndexTree);
// 	    if (stTree->stDephs[inIndexTree] <= inIndex && stNodes[inIndex] != -1)
//             {  //printf("inIndex %d inIndexTree %d stDephs %d \n",inIndex,inIndexTree, stTree->stDephs[inIndexTree]);
// 	      for (inIndexInsert = (g->nvertices-1); inIndexInsert > inIndexTree; inIndexInsert--) 
//               {
// 	        stTree->stNodes[inIndexInsert] = stTree->stNodes[inIndexInsert - 1];
// 	        stTree->stDephs[inIndexInsert] = stTree->stDephs[inIndexInsert - 1];	      
// 	      }
// 	      stTree->stNodes[inIndexTree] = -1;
// 	    }	    
// 	    if (stTree->stNodes[inIndexTree] == -1) {
// 	      stTree->stNodes[inIndexTree] = stNodes[inIndex];
// 	      stTree->stDephs[inIndexTree] = inIndex+1;
// 	      stTree->inNumberNodes++;
// 	      inIndex++;
// 	    }
// 	    if (stTree->stNodes[inIndexTree] == stNodes[inIndex]) {
// 	      inIndex++;	    
// 	    }
// 	    inIndexTree++;
// 	  } 
// 	}
// 	free(stNodes);
// 	free(stIndex);
// 	return stTree;
// 	
// }

void BuscaProfundidade(GraphNode *G, int *stNodes, int * stDepths, int ini, int *posicao, int depthAncestral){
    int num = 1;
    int i;
    AdjacentNode * aux = Malloc(AdjacentNode,1);
    G[ini].flag = true;
    stNodes[posicao[0]] = G[ini].inNodeName;
    stDepths[posicao[0]] = depthAncestral+1;	 	
    //printf("no %d profundidade %d posicao %d \n", ini, stDepths[posicao[0]], posicao[0]);     	 
    	
    	
    for (i= 0; i < G[ini].inNumberAdjacents; i++)
    {
  		aux->inNodeName = G[ini].ptPointer[i].inNodeName;
  		if (G[aux->inNodeName].flag == false)
  		{
			posicao[0]++;
  			BuscaProfundidade(G, stNodes, stDepths, aux->inNodeName, posicao,(depthAncestral+1));
                }
    }//fim do for
  } //fim BuscaProfundidade

//---------------------------------------------------------------------------
Tree *Prim(graph *g, int start, int inRestriction) {
	int i;
	int j;
	int inIndex;
	int inIndexInsert;
	int inIndexTree;
	//int node;
	int node_parent;
	//int *stIndex;
	//int *stNodes;
	Tree *stTree = Malloc(Tree, 1);
	
	CreateSpanningTree(g, start, inRestriction);
	
	stTree->stNodes = Malloc(int, inNumberNodesAT);
	stTree->stDephs = Malloc(int, inNumberNodesAT);
	//stIndex = Malloc(int, 1);
	stTree->inNumberNodes = inNumberNodesAT;
	stTree->inTreeName = 0;
	//stNodes = Malloc(int, g->nvertices);
	
	 for(i =0; i< inNumberNodesAT; i++)
    	 {
		node_parent = parent[i];
		//printf("start %d, i %d, node_parent %d \n", start, i, node_parent);
		if (node_parent != -1)	
		{
			tree1[i].ptPointer[tree1[i].inNumberAdjacents].inNodeName = node_parent;
			tree1[i].inNumberAdjacents++;
			tree1[node_parent].ptPointer[tree1[node_parent].inNumberAdjacents].inNodeName = i;
			tree1[node_parent].inNumberAdjacents++;
		}
    	 }
	/* for(i =0; i< inNumberNodesAT; i++)
    	 {
		printf("node %d: ",i);
		for(j =0; j< tree1[i].inNumberAdjacents; j++)
		{	
	
			printf("%d, ",tree1[i].ptPointer[j].inNodeName);
		 
		}
		printf("\n");	
    	 }*/
	
	//free(stNodes);
	//free(stIndex);
	inIndexInsert = 0;
	BuscaProfundidade(tree1, stTree->stNodes, stTree->stDephs, start, &inIndexInsert, 0);
// 	print_tree( stTree, "Arvore", 0, 0 );
	return stTree;
	
}



//---------------------------------------------------------------------------

void LoadAdjacentTable() {
   	ifstream file;     //arquivo de entrada
  	int node_init;     //no de inicio na aresta
  	int node_end;      //no final na aresta
  	float cost;       //custo da aresta
	
  	
  	int i;
    //abrindo arquivo para leitura dos nos
  	//printf("lendo grafo \n");
   file.open(GraphArq);
  //printf("depois da abertura do arquivo \n");
   	
   if (!file.fail())
   { 
	file>>inNumberNodesAT;
	
   	 initialize_graph(&g);
	g.nvertices = inNumberNodesAT;
      if ((stNodesAT = Malloc(GraphNode,inNumberNodesAT))!=NULL)
      {		tree1 = Malloc(GraphNode,inNumberNodesAT);
     	   for(i =0; i< inNumberNodesAT; i++)
    	   {		
		tree1[i].inNodeName = i;  //NOME DE CADA SETOR
    		tree1[i].inNumberAdjacents = 0;
		tree1[i].flag = false;
    		tree1[i].ptPointer = Malloc (AdjacentNode, inRestriction);
	//	printf("inRestriction %d\n", inRestriction);
    		stNodesAT[i].inNodeName = i;  //NOME DE CADA SETOR
    		stNodesAT[i].inNumberAdjacents = 0;
    		 if((stNodesAT[i].ptPointer = Malloc (AdjacentNode, inNumberNodesAT))==NULL)
		         printf("ptPointer nao alocado");
             	          // stNodesAT[i].flag = false;
    	   }
    		printf("depois de atribuir nomes \n");
            while (!file.eof())
    	    {
    	     // leitura das variaveis para dados do grafo
               file>>node_init>>node_end>>cost;
	     //  printf("no inicio %d no final %d custo %f\n",node_init,node_end,cost);
	       //printf("numero adjacentes %d\n",stNodesAT[node_init].inNumberAdjacents);
               stNodesAT[node_init].ptPointer[stNodesAT[node_init].inNumberAdjacents].inNodeName=node_end;
               stNodesAT[node_init].ptPointer[stNodesAT[node_init].inNumberAdjacents].inWeight = cost;
               stNodesAT[node_init].inNumberAdjacents++;
	       
	       stNodesAT[node_end].ptPointer[stNodesAT[node_end].inNumberAdjacents].inNodeName=node_init;
               stNodesAT[node_end].ptPointer[stNodesAT[node_end].inNumberAdjacents].inWeight = cost;
               stNodesAT[node_end].inNumberAdjacents++;
	       insert_edge(&g, node_init, node_end, FALSE, cost);
    	    }//fim while
		for(i =0; i< inNumberNodesAT; i++)
    	   {
    			   if (  stNodesAT[i].inNumberAdjacents == 0)
				printf ("node %d \n", stNodesAT[i].inNodeName);
    	    }
	//	print_graph(&g);
      } // fim if malloc graph
      else 
      {
        cout << " Malloc graph \n";
      }
      
      file.close();
      
   }
   else
   		cout << "Error opening file graph" << endl;    

}

//**********  Le de um arquivo as coordenadas euclidianas do grafo e constr�i as arestas ***************//

void LoadEuclideanGraph(int inNumberNodesParam) {
    ifstream file;     //arquivo de entrada
    int node_init;     //no de inicio na aresta
    int node_end;      //no final na aresta
    int instances;
	float x,y;
    float cost;       //custo da aresta

    int i, j;
    if (GraphArq != NULL)
    {
    	file.open(GraphArq);
    	//printf("LoadAdjacentTable - Depois de abrir arquivo...\n");
    	if (!file.fail()) {
	 file>>instances;
       	 file>>inNumberNodesAT;
       	 if ((stNodesAT = Malloc(GraphNode, inNumberNodesAT))!=NULL) {
            //printf("LoadAdjacentTable - Alocacao do grafo\n");
            for(i =0; i< inNumberNodesAT; i++) {
                stNodesAT[i].inNodeName = i;
                stNodesAT[i].inNumberAdjacents = inNumberNodesAT-1;
                if((stNodesAT[i].ptPointer = Malloc(AdjacentNode, inNumberNodesAT))!=NULL) {
                    for (j=0; j< inNumberNodesAT; j++) {
                        stNodesAT[i].ptPointer[j].inNodeName=j;
                        stNodesAT[i].ptPointer[j].inWeight = -1;
                    }
                }
                else
                    printf("ptPointer nao alocado");
                // stGraph[i].flag = false;
            }
		i =0;
		while (i < inNumberNodesAT) {
		   file>>x>>y;
		   // printf("x %f y %f \n",x,y);
			stNodesAT[i].x = x;
			stNodesAT[i].y = y;
			i++;
		}
		for (i =0; i < inNumberNodesAT-1; i++)
			for (j=i+1; j < inNumberNodesAT; j++)
			{
				stNodesAT[i].ptPointer[j].inWeight = sqrt(pow((stNodesAT[i].x-stNodesAT[j].x),2)+pow((stNodesAT[i].y-stNodesAT[j].y),2));
				stNodesAT[j].ptPointer[i].inWeight = sqrt(pow((stNodesAT[i].x-stNodesAT[j].x),2)+pow((stNodesAT[i].y-stNodesAT[j].y),2));
			}	
          } // fim if malloc graph
         else {
            cout << " Malloc graph \n";
       	 }
        	file.close();
    	}
    }
    else {
        cout << "Arquivo inexistente \n";
    }
    
}

int *GetAdjacentNodes(int inNodeParam) {
  int inIndex;
  int inPosition;
  int *inAdjacentNodes;
  inIndex = inNodeParam;//AdjacentBinarySearch (stNodesAT, inNodeParam, inNumberNodesAT - 1);
  if (inIndex >= 0) {
    inAdjacentNodes = Malloc(int, stNodesAT[inIndex].inNumberAdjacents);
    inPosition = 0;
    while (inPosition < stNodesAT[inIndex].inNumberAdjacents) {
      inAdjacentNodes[inPosition] = stNodesAT[inIndex].ptPointer[inPosition].inNodeName;
      inPosition++;
    }
    return inAdjacentNodes;
  }
  else
    return NULL;
}

float GetWeight(int inNodeParam, int inAdjacentParam) {
  int inIndex;
  int inPosition;
  AdjacentNode *stNode;
  inIndex = inNodeParam;//AdjacentBinarySearch (stNodesAT, inNodeParam, inNumberNodesAT - 1);
  if (inIndex >= 0) {
    inPosition = 0;
    stNode = stNodesAT[inIndex].ptPointer;
    while (inPosition < stNodesAT[inIndex].inNumberAdjacents && stNodesAT[inIndex].ptPointer[inPosition].inNodeName != inAdjacentParam) {
      inPosition++;
    }

    if (inPosition < stNodesAT[inIndex].inNumberAdjacents)
      return stNodesAT[inIndex].ptPointer[inPosition].inWeight;
    else
      return 0;
  }
  else
    return 0;
}

int GetParentIndex (Tree *stTreeParam, int inIndexParam) {
    int inIndexRaiz = inIndexParam;
    while (inIndexRaiz > 0 && stTreeParam->stDephs[inIndexRaiz] > stTreeParam->stDephs[inIndexParam] - 1) {
      inIndexRaiz--;
    }
    if (stTreeParam->stDephs[inIndexRaiz] > stTreeParam->stDephs[inIndexParam] - 1)
      return -1;
    else
      return inIndexRaiz;
}

int GetEdge(int inNodeParam, int inAdjacentParam) {
  int inIndex;
  int inPosition;
  AdjacentNode *stNode;
  inIndex = inNodeParam;//AdjacentBinarySearch (stNodesAT, inNodeParam, inNumberNodesAT - 1);
  if (inIndex >= 0) {
    inPosition = 0;
    stNode = stNodesAT[inIndex].ptPointer;
    while (inPosition < stNodesAT[inIndex].inNumberAdjacents && stNodesAT[inIndex].ptPointer[inPosition].inNodeName != inAdjacentParam) {
      inPosition++;
    }

    if (inPosition < stNodesAT[inIndex].inNumberAdjacents)
      return 1;
    else
      return 0;
  }
  else
    return 0;
}

int GetNumberAdjacentNodes(int inNodeParam) {
  int inIndex;

  inIndex = inNodeParam;//AdjacentBinarySearch (stNodesAT, inNodeParam, inNumberNodesAT - 1);
  if (inIndex >= 0){
    return stNodesAT[inIndex].inNumberAdjacents;
  }
  else {
    return 0;
  }
}

int AdjacentBinarySearch (GraphNode *stNodesParam, int inSearchParam, int inLastParam) {
  int inFirst = 0;
  int inMidle = (inFirst + inLastParam) / 2;
  while ((inFirst <= inLastParam) && (stNodesParam[inMidle].inNodeName!= inSearchParam)){
    if(stNodesParam[inMidle].inNodeName > inSearchParam){
      inLastParam = inMidle - 1;
    }//Busca na parte superior
    else
    if(stNodesParam[inMidle].inNodeName < inSearchParam){
       inFirst = inMidle + 1;
    }//Busca na parte inferior
    inMidle = (inFirst + inLastParam) / 2;
  }
  if(stNodesParam[inMidle].inNodeName == inSearchParam)
    return inMidle; //encontrou, retorna a posi��o
  else
    return -1;  //n�o encontrou, retorna um aviso
}

void ReleaseAdjacentTable() {
  AdjacentNode *ptNode;
  int inIndex;
  inIndex = 0 ;
  while (inIndex < inNumberNodesAT) {
    free(stNodesAT[inIndex].ptPointer);
    inIndex++;
  }
  free(stNodesAT);
}

//---------------------------------------------------------------------------

void LoadPositionMatrix(GraphNode *graph)
{ 
  inNumberNodesPI = inNumberNodesAT;
//printf("innumvernodespi %d\n",inNumberNodesPI);
  if((PI = (PositionMatrix *) malloc(inNumberNodesPI * sizeof(PositionMatrix)))!=NULL)
    {//printf("ANtes Matriz PI alocada \n");
            int inNode = 0;
            int i;
	    int inColunm;
            for( i=0; i<inNumberNodesAT; i++)
            {
        	PI[inNode].inNodeName = graph[i].inNodeName;
  	    	PI[inNode].inNumberColunms = 0;
          	PI[inNode].stColunms = (PositionColunm **) malloc ((inMaxColunm) * sizeof(PositionColunm *));
		for (inColunm = 0; inColunm < inMaxColunm;inColunm++)
		{
                	PI[inNode].stColunms[inColunm] = Malloc(PositionColunm, 1);
		}
		inNode++;
		
            }
//printf("Matriz PI alocada \n");
          	pi = Malloc(int, inMaxColunm);
          	inNumberNodespi = inMaxColunm;
		

          	for(i=0; i<inNumberNodespi; i++)

          		pi[i] = -1;
    }

    else
      cout << "Malloc PI\n";
}


void ReInsertPop(Forest **stForestsParam, Forest *stForestParam, int *stPopulationParam) {
    //printf("incomSize %d inPopSize %d\n", inComSize, inPopSize);
    stForestsParam[inComSize] = stForestParam;
    stPopulationParam[inPopSize] = inComSize;
    inPopSize++;
    
    
    if (fpBestFitness > stForestParam->fpFitness)
        fpBestFitness =  stForestParam->fpFitness;
    if (fpWorstFitness < stForestsParam[stPopulationParam[inPopSize - 1]]->fpFitness)
        fpWorstFitness = stForestsParam[stPopulationParam[inPopSize - 1]]->fpFitness;
    
    if (inComSize < inMaxColunm)
        inComSize++;
}

//************* funcao para remontagem da matriz PI **************//
Forest ** reLoadPositionMatrix(Forest **stForestsParam, int inMaxPopParam, int *stPopulationParam) {
    int inNode = 0;
    int i, j;
    Forest * stForest;
    Forest **stForestsAux;	
    Tree *stTree;
    inCurrentForestName = 0;
    int desalocar = inComSize;
  // printf("inComSize %d\n", inComSize);
    inComSize = 0;
    inPopSize = 0;
    //fpWorstFitness = -100000.00; //para problema de minimizar
    stForestsAux = Malloc(Forest*, inMaxColunm);			
   //printf("innode %d\n", inNode);
    //Libera espaço da PI
    for( i=0; i<inNumberNodesAT; i++) {
        PI[i].inNumberColunms = 0;
    }
    
    inNumberNodespi = inMaxColunm;
    //Libera espaço da pi
    for(i=0; i<inMaxColunm; i++) {
        pi[i] = -1;
    }
    for (i=0; i < inMaxPopParam; i++) {
        inCurrentForestName ++;
        //stForest = CreateForest(1, inCurrentForestName);
	stForest = Malloc(Forest, 1);
   	stForest->inNumberTrees = 1;
    	stForest->stTrees = Malloc(Tree*, stForest->inNumberTrees);
    	stForest->inForestName = inCurrentForestName;
  
        stForest->fpFitness = stForestsParam[stPopulationParam[i]]->fpFitness;
        stTree = Malloc(Tree, 1);
        stTree->inTreeName = stForestsParam[stPopulationParam[i]]->stTrees[0]->inTreeName;
        stTree->inNumberNodes = stForestsParam[stPopulationParam[i]]->stTrees[0]->inNumberNodes;
        stTree->stNodes = Malloc(int, stForestsParam[stPopulationParam[i]]->stTrees[0]->inNumberNodes);
        stTree->stDephs = Malloc(int, stForestsParam[stPopulationParam[i]]->stTrees[0]->inNumberNodes);
        
        for (inNode = 0; inNode < stForestsParam[stPopulationParam[i]]->stTrees[0]->inNumberNodes; inNode++) {
            stTree->stNodes[inNode] = stForestsParam[stPopulationParam[i]]->stTrees[0]->stNodes[inNode];
            stTree->stDephs[inNode] = stForestsParam[stPopulationParam[i]]->stTrees[0]->stDephs[inNode];
            AddPosition(stForestsParam[stPopulationParam[i]]->stTrees[0]->stNodes[inNode], inCurrentForestName, stForestsParam[stPopulationParam[i]]->stTrees[0]->inTreeName, inNode, stForestsParam[stPopulationParam[i]]->stTrees[0]->stDephs[inNode]);
        }
        stForest->stTrees[0] = stTree;
	//stForestsParam[i]->inForestName = inCurrentForestName;
        ReInsertPop(stForestsAux, stForest, stPopulationParam);
        SetGenitor(inCurrentForestName, -1);
     }
	//printf("inComSize %d, inMaxColumn-inMaxPopParam %d \n", inComSize, (inMaxColumn-inMaxPopParam));
    //ReleaseForests(stForestsParam);
	int inIndex = 0;
  while (inIndex < (desalocar)) {
    //printf("inIndex %d \n", inIndex);
    ReleaseForest(stForestsParam[inIndex]);
    free(stForestsParam[inIndex]);	
    inIndex++;
  }
  free(stForestsParam);
	return(stForestsAux);
}

void ReleasePositionMatrix() {
 int inIndex;
  int inIndex2;
  for(inIndex = 0; inIndex < inNumberNodesPI; inIndex++) 
  {
  	for(inIndex2 = 0; inIndex2 < inMaxColunm; inIndex2++) 
  	{
		//printf("inIndex %d \n",inIndex);
	 	free(PI[inIndex].stColunms[inIndex2]);
  	}	
	//PIParam[inIndex].stColunms[inColunm]->inForest = inForestParam;
  
	free(PI[inIndex].stColunms);
  }	

 free(PI);
};

void SetGenitor(int inForestParam, int inGenitorParam) {
  int * piAux;
  int inIndex;
  if (((inForestParam - inFirstForest) % (inMaxColunm-1) == 0) && (inForestParam != inFirstForest)) {
        reloadPi = true;
    }
  //printf("indice de armazenamento %d \n",(inForestParam - inFirstForest));
  pi[inForestParam - inFirstForest] = inGenitorParam;
}

PositionColunm *GetPosition(int inNodeParam, int inForestParam) {
  int inIndex;
  int inPosition;
  int inForest;
  PositionColunm *stColunm;
  inForest = inForestParam;
  inIndex = inNodeParam;//PositionBinarySearch (PI, inNodeParam, inNumberNodesPI - 1);
  if (inIndex >= 0)
  { //printf("inicial inIndex %d inForest %d \n",inIndex, inForest);
    inPosition = ColunmBinarySearch (PI, inIndex, inForest, PI[inIndex].inNumberColunms - 1);
    int i = 0;
    while (inPosition < 0) 
    {
        inForest = pi[inForest - inFirstForest];
	//printf("inIndex %d inForest %d \n",inIndex, inForest);
        inPosition = ColunmBinarySearch (PI, inIndex, inForest, PI[inIndex].inNumberColunms - 1);
    }
    stColunm = Malloc(PositionColunm, 1);
    stColunm->inForest = PI[inIndex].stColunms[inPosition]->inForest;
    stColunm->inTree = PI[inIndex].stColunms[inPosition]->inTree;
    stColunm->inIndex = PI[inIndex].stColunms[inPosition]->inIndex;
    stColunm->inDeph = PI[inIndex].stColunms[inPosition]->inDeph;
    return stColunm;
  }
  else
    return NULL;
}

void AddPosition(int inNodeParam, int inForestParam, int inTreeParam, int inIndexParam, int inDephParam) {
  int inIndex;
  int inColunm;
  //PositionColunm *AuxColunm;

  inIndex = inNodeParam;//PositionBinarySearch (PI, inNodeParam, inNumberNodesPI - 1);
  //printf("depois de position binary search \n");
  if (inIndex >= 0) 
  {
	inColunm = PI[inIndex].inNumberColunms;
	//printf("inIndex %d inColunm %d \n", inIndex, inColunm);
	PI[inIndex].stColunms[inColunm]->inForest = inForestParam;
     	PI[inIndex].stColunms[inColunm]->inTree = inTreeParam;
     	PI[inIndex].stColunms[inColunm]->inIndex = inIndexParam;
     	PI[inIndex].stColunms[inColunm]->inDeph = inDephParam;
    	//printf("AddPosition inIndex %d PI[inIndex].inNumberColunms %d \n",inIndex,PI[inIndex].inNumberColunms);
    	//PI[inIndex].stColunms[PI[inIndex].inNumberColunms] = AuxColunm;
    	PI[inIndex].inNumberColunms++;
   }
}

int PositionBinarySearch (PositionMatrix *stMatrixParam, int inSearchParam, int inLastParam) {
  int inFirst = 0;
  int inMidle = (inFirst + inLastParam) / 2;
  while ((inFirst <= inLastParam) && (stMatrixParam[inMidle].inNodeName!= inSearchParam)){
    if(stMatrixParam[inMidle].inNodeName > inSearchParam){
      inLastParam = inMidle - 1;
    }//Busca na parte superior
    else
    if(stMatrixParam[inMidle].inNodeName < inSearchParam){
       inFirst = inMidle + 1;
    }//Busca na parte inferior
    inMidle = (inFirst + inLastParam) / 2;
  }
  if(stMatrixParam[inMidle].inNodeName == inSearchParam)
    return inMidle; //encontrou, retorna a posi��o
  else
    return -1;  //n�o encontrou, retorna um aviso

}

int ColunmBinarySearch (PositionMatrix  *stMatrixParam, int inIndexParam, int inSearchParam, int inLastParam) {
  int inFirst = 0;
  int inMidle = (inFirst + inLastParam) / 2;
  //printf("inMidle %d inIndexParam %d inSearchParam %d stMatrixParam[inIndexParam].stColunms[inMidle]->inForest %d\n",inMidle, inIndexParam,inSearchParam,stMatrixParam[inIndexParam].stColunms[inMidle]->inForest);
  while ((inFirst <= inLastParam) && (stMatrixParam[inIndexParam].stColunms[inMidle]->inForest != inSearchParam))
  {
    if(stMatrixParam[inIndexParam].stColunms[inMidle]->inForest > inSearchParam){
      inLastParam = inMidle - 1;
    }//Busca na parte superior
    else
    if(stMatrixParam[inIndexParam].stColunms[inMidle]->inForest < inSearchParam){
      inFirst = inMidle + 1;
    }//Busca na parte inferior
    inMidle = (inFirst + inLastParam) / 2;
    //printf("inLastParam %d inMidle %d inIndexParam %d\n",inLastParam, inMidle, inIndexParam);
  }
  //printf("colunmBinarySearch inMidle %d\n",inMidle);
  if(stMatrixParam[inIndexParam].stColunms[inMidle]->inForest == inSearchParam)
    return inMidle; //encontrou, retorna a posi��o
  else
    return -1;  //n�o encontrou, retorna um aviso
}


Forest *CreateForest(int inNumberTreesParam, int inForestNameParam) {
  int inIndex = 0;
  Forest *stForest = Malloc(Forest, 1);
  stForest->inNumberTrees = inNumberTreesParam;
  stForest->stTrees = Malloc(Tree*, stForest->inNumberTrees);
  stForest->inForestName = inForestNameParam;
  stForest->fpFitness = 0.0;
  while (inIndex < inNumberTreesParam) {
    stForest->stTrees[inIndex] = NULL;
    inIndex++;
  }
  return stForest;
};

void ReleaseForest(Forest *stForestParam) {
  int inIndex = 0;
  while (inIndex < stForestParam->inNumberTrees) {
    if (stForestParam->stTrees[inIndex] != NULL) {
      free(stForestParam->stTrees[inIndex]->stNodes);
      free(stForestParam->stTrees[inIndex]->stDephs);
      //
      free(stForestParam->stTrees[inIndex]);
      stForestParam->stTrees[inIndex] = NULL;
    }
    inIndex++;
  }


  free(stForestParam->stTrees);
};

Tree *GetTree(Forest *stForestParam, int inTreeParam) {
  int inIndex;

  Tree *stTree = Malloc(Tree, 1);

  //Cria a estrutura da �rvore e copia os flags
  stTree->inNumberNodes = stForestParam->stTrees[inTreeParam]->inNumberNodes;
  stTree->stNodes = Malloc(int, stTree->inNumberNodes);
  stTree->stDephs = Malloc(int, stTree->inNumberNodes);
  stTree->inTreeName = inTreeParam;
  //Copia os nodos da �rvore
  inIndex = 0;
  while (inIndex < stTree->inNumberNodes) {
    stTree->stNodes[inIndex] = stForestParam->stTrees[inTreeParam]->stNodes[inIndex];
    stTree->stDephs[inIndex] = stForestParam->stTrees[inTreeParam]->stDephs[inIndex];
    inIndex++;
  }
  return  stTree;
}

void SetTree(Forest *stForestParam, Tree *stTreeParam, int inTreeParam) {
  int inIndex;
  //Cria a estrutura da �rvore e copia os flags
  stForestParam->stTrees[inTreeParam]->inNumberNodes = stTreeParam->inNumberNodes;
  stForestParam->stTrees[inTreeParam]->stNodes = Malloc(int, stTreeParam->inNumberNodes);
  stForestParam->stTrees[inTreeParam]->stDephs = Malloc(int, stTreeParam->inNumberNodes);
  stForestParam->stTrees[inTreeParam]->inTreeName = inTreeParam;
  //Copia os nodos da �rvore
  inIndex = 0;
  while (inIndex < stTreeParam->inNumberNodes) {
    stForestParam->stTrees[inTreeParam]->stNodes[inIndex] = stTreeParam->stNodes[inIndex];
    stForestParam->stTrees[inTreeParam]->stDephs[inIndex] = stTreeParam->stDephs[inIndex];
    inIndex++;
  }
}

//---------------------------------------------------------------------------

int GetRamdomNumber(int inLow, int inHigh) {
  if (inHigh <= inLow)
    return  inLow;
  else
    return (int) random() % inHigh + inLow;
}

//double GetNumberReal(double inLow, double inHigh) {
//  return (double) random() % inHigh + inLow;
//}


//---------------------------------------------------------------------------

int GetRange (Tree *stTreeFromParam, int inIndexPParam) {
  int inIndex;
  int inLength;

  inIndex = inIndexPParam + 1;
  inLength = stTreeFromParam->inNumberNodes;
  while (inIndex < inLength && stTreeFromParam->stDephs[inIndexPParam] < stTreeFromParam->stDephs[inIndex])
    inIndex++;
  return --inIndex;
}

Tree *CopySubTree (Tree *stTreeFromParam, int inIndexPParam, int inIndexLParam, int inDephAParam) {
  int inIndex;
  int inTempIndex;
  Tree *stTempTree = Malloc(Tree, 1);
  stTempTree->inNumberNodes = inIndexLParam - inIndexPParam + 1;
  stTempTree->stNodes = Malloc(int, inIndexLParam - inIndexPParam + 1);
  stTempTree->stDephs = Malloc(int, inIndexLParam - inIndexPParam + 1);
  inTempIndex = 0;
  inIndex = inIndexPParam;
  while (inIndex <= inIndexLParam) {
    stTempTree->stNodes[inTempIndex] = stTreeFromParam->stNodes[inIndex];
    stTempTree->stDephs[inTempIndex] = stTreeFromParam->stDephs[inIndex] - stTreeFromParam->stDephs[inIndexPParam] + inDephAParam + 1;
    inIndex++;
    inTempIndex++;
  }
  return stTempTree;
}

Tree *ModifySubTree (Tree *stTreeFromParam, int inIndexPParam, int inIndexLParam, int inIndexRParam, int inDephAParam) {
  int inTempIndex;
  int inIndex;
  int inRoot;
  int inRootDeph;
  int inDeph1;
  int inDeph2;
  int inIndexLR = GetRange(stTreeFromParam, inIndexRParam);
  int inTempTreeSize = inIndexRParam - inIndexPParam + inIndexLParam - inIndexLR;
  int inTop = inIndexRParam;
  int inBotton = inIndexLR;

  Tree *stTempTree = Malloc(Tree, 1);
  stTempTree->inNumberNodes = inTempTreeSize;
  stTempTree->stNodes = Malloc(int, inTempTreeSize);
  stTempTree->stDephs = Malloc(int, inTempTreeSize);

  inTempIndex = 0;
  while (inIndexPParam < inTop) {
    //Determina o indice da raiz da sub-�rvore a ser copiada

    inRootDeph = stTreeFromParam->stDephs[inTop] - 1;
    inRoot = inTop;
    while (stTreeFromParam->stDephs[inRoot] > inRootDeph)
      if (inRoot > 1)
        inRoot--;

    //Copia a parte anterior � sub-�rvore a ser "pulada"
    inDeph1 = stTreeFromParam->stDephs[inIndexRParam] - stTreeFromParam->stDephs[inRoot];
    inIndex = inRoot;
    while (inIndex < inTop) {
      stTempTree->stNodes[inTempIndex] = stTreeFromParam->stNodes[inIndex];
      inDeph2 = stTreeFromParam->stDephs[inIndex] - stTreeFromParam->stDephs[inRoot];
      stTempTree->stDephs[inTempIndex] = inDeph2 + inDeph1 + inDephAParam + 1;
      inIndex++;
      inTempIndex++;
    }

    //Atualiza o Topo
    inTop = inRoot;

    //Copia a parte posterior � sub-�rvore a ser "pulada"
    inIndex = inBotton + 1;
    while (inIndex < stTreeFromParam->inNumberNodes && stTreeFromParam->stDephs[inIndex] > inRootDeph) {
      stTempTree->stNodes[inTempIndex] = stTreeFromParam->stNodes[inIndex];
      inDeph2 = stTreeFromParam->stDephs[inIndex] - stTreeFromParam->stDephs[inRoot];
      stTempTree->stDephs[inTempIndex] = inDeph2 + inDeph1 + inDephAParam + 1;
      inIndex++;
      inTempIndex++;
    }

    //Atualiza o Topo
    inBotton = --inIndex;
  }
  return stTempTree;
}

Tree *BuildTreeTo (Tree *stTreeToParam, Tree *stTreeTempParam, int inIndexAParam) {
  int inTreeToSize = stTreeToParam->inNumberNodes;
  int inTreeTempSize = stTreeTempParam->inNumberNodes;
  int inIndexL = GetRange(stTreeToParam, inIndexAParam);
  int inIndex;
  Tree *stTempTree = Malloc(Tree, 1);
  stTempTree->inTreeName = stTreeToParam->inTreeName;
  stTempTree->inNumberNodes = inTreeToSize + inTreeTempSize;
  stTempTree->stNodes = Malloc(int, inTreeToSize + inTreeTempSize);
  stTempTree->stDephs = Malloc(int, inTreeToSize + inTreeTempSize);
  inIndex = 0;
  while (inIndex <= inIndexAParam) {
    stTempTree->stNodes[inIndex] = stTreeToParam->stNodes[inIndex];
    stTempTree->stDephs[inIndex] = stTreeToParam->stDephs[inIndex];
    inIndex++;
  }
  inIndex = 0;
  while (inIndex < inTreeTempSize) {
    stTempTree->stNodes[inIndexAParam + inIndex + 1] = stTreeTempParam->stNodes[inIndex];
    stTempTree->stDephs[inIndexAParam + inIndex + 1] = stTreeTempParam->stDephs[inIndex];
    inIndex++;
  }
  inIndex = inIndexAParam + 1;
  while (inIndex < inTreeToSize) {
    stTempTree->stNodes[inTreeTempSize + inIndex] = stTreeToParam->stNodes[inIndex];
    stTempTree->stDephs[inTreeTempSize + inIndex] = stTreeToParam->stDephs[inIndex];
    inIndex++;
  }
  return stTempTree;
}

Tree *BuildModifiedTreeTo (Tree *stTreeToParam, Tree *stTempTreeParam1, Tree *stTempTreeParam2, int inIndexAParam) {
  int inTreeToSize = stTreeToParam->inNumberNodes;
  int inTempTreeSize1 = stTempTreeParam1->inNumberNodes;
  int inTempTreeSize2 = stTempTreeParam2->inNumberNodes;
  int inIndexL = GetRange(stTreeToParam, inIndexAParam);
  int inIndex;
  Tree *stTempTree = Malloc(Tree, 1);
  stTempTree->inTreeName = stTreeToParam->inTreeName;
  stTempTree->inNumberNodes = inTreeToSize + inTempTreeSize1 + inTempTreeSize2;
  stTempTree->stNodes = Malloc(int, inTreeToSize + inTempTreeSize1 + inTempTreeSize2);
  stTempTree->stDephs = Malloc(int, inTreeToSize + inTempTreeSize1 + inTempTreeSize2);
  inIndex = 0;
  while (inIndex <= inIndexAParam) {
    stTempTree->stNodes[inIndex] = stTreeToParam->stNodes[inIndex];
    stTempTree->stDephs[inIndex] = stTreeToParam->stDephs[inIndex];
    inIndex++;
  }
  inIndex = 0;
  while (inIndex < inTempTreeSize1) {
    stTempTree->stNodes[inIndexAParam + inIndex + 1] = stTempTreeParam1->stNodes[inIndex];
    stTempTree->stDephs[inIndexAParam + inIndex + 1] = stTempTreeParam1->stDephs[inIndex];
    inIndex++;
  }
  inIndex = 0;
  while (inIndex < inTempTreeSize2) {
    stTempTree->stNodes[inTempTreeSize1 + inIndexAParam + inIndex + 1] = stTempTreeParam2->stNodes[inIndex];
    stTempTree->stDephs[inTempTreeSize1 + inIndexAParam + inIndex + 1] = stTempTreeParam2->stDephs[inIndex];
    inIndex++;
  }
  inIndex = inIndexAParam + 1;
  while (inIndex < inTreeToSize) {
    stTempTree->stNodes[inTempTreeSize1 + inTempTreeSize2 + inIndex] = stTreeToParam->stNodes[inIndex];
    stTempTree->stDephs[inTempTreeSize1 + inTempTreeSize2 + inIndex] = stTreeToParam->stDephs[inIndex];
    inIndex++;
  }
  return stTempTree;
}

Tree *BuildTreeFrom (Tree *stTreeFromParam, int inIndexPParam, int inIndexLParam) {
  int inTreeFromSize = stTreeFromParam->inNumberNodes;
  int inIndex;
  int inIndexJ;
  Tree *stTempTree = Malloc(Tree, 1);
  stTempTree->inTreeName = stTreeFromParam->inTreeName;
  stTempTree->inNumberNodes = inTreeFromSize - (inIndexLParam - inIndexPParam + 1);
  stTempTree->stNodes = Malloc(int, inTreeFromSize - (inIndexLParam - inIndexPParam + 1));
  stTempTree->stDephs = Malloc(int, inTreeFromSize - (inIndexLParam - inIndexPParam + 1));
  inIndex = 0;
  while (inIndex < inIndexPParam) {
    stTempTree->stNodes[inIndex] = stTreeFromParam->stNodes[inIndex];
    stTempTree->stDephs[inIndex] = stTreeFromParam->stDephs[inIndex];
    inIndex++;
  }

  inIndexJ = inIndexLParam + 1;
  while (inIndexJ < inTreeFromSize) {
    stTempTree->stNodes[inIndex] = stTreeFromParam->stNodes[inIndexJ];
    stTempTree->stDephs[inIndex] = stTreeFromParam->stDephs[inIndexJ];
    inIndexJ++;
    inIndex++;
  }
  return stTempTree;
}

//---------------------------------------------------------------------------

int GetDegree (Tree *stTreeFromParam, int inIndexAParam) {
  int inIndex;
  int inLength;
  int inCounter;
  inCounter = 0;
  inIndex = inIndexAParam + 1;
  inLength = stTreeFromParam->inNumberNodes;
  while (inIndex < inLength && stTreeFromParam->stDephs[inIndexAParam] < stTreeFromParam->stDephs[inIndex]) {
    if (stTreeFromParam->stDephs[inIndex] == stTreeFromParam->stDephs[inIndexAParam] + 1)
      inCounter++;
    inIndex++;
  }
  return inCounter;
}

double InitFitness (Forest *stForestParam) {
  int inIndex;
  int node1,node2;
  int inTree;
  int inSize;
  double fpSum;
  int inNumberTrees = stForestParam->inNumberTrees;
  int stRoots[inNumberNodesAT+1];
  fpSum = 0.0;
  inTree = 0;
	//print_forest(stForestParam);
  while (inTree < inNumberTrees) 
  {
    inSize = stForestParam->stTrees[inTree]->inNumberNodes;
    
    stRoots[1] = stForestParam->stTrees[inTree]->stNodes[0];	
    //printf("inTree %d \n",inTree);
    for(inIndex = 1; inIndex < inSize; inIndex++)
    {
	stRoots[stForestParam->stTrees[inTree]->stDephs[inIndex]] = stForestParam->stTrees[inTree]->stNodes[inIndex];
	node1 = stForestParam->stTrees[inTree]->stNodes[inIndex];
	node2 = stRoots[stForestParam->stTrees[inTree]->stDephs[inIndex]-1]; 
	//printf("node1 %d,node2 %d\n",node1,node2);
        fpSum += GetWeight(node1,node2);
     
    }
    inTree++;
  }
  return fpSum;
}

//double Fitness (Forest *stForestParam) {
//  return stForestParam->fpFitness + inDifference;
//}
/*

double Fitness (Forest *stForestParam) {
  int inIndex;
  double inMeam;
  double inVariance;
  int inNumberTrees;
  int *inSizes;

  inNumberTrees = stForestParam->inNumberTrees;
  inSizes = Malloc(int, inNumberTrees);
  inIndex = 0;
  while (inIndex < inNumberTrees) {
    inSizes[inIndex] = stForestParam->stTrees[inIndex]->inNumberNodes;
    inIndex++;
  }
  inIndex = 0;
  inMeam = 0;
  while (inIndex < inNumberTrees) {
    inMeam += inSizes[inIndex];
    inIndex++;
  }
  inMeam /= inNumberTrees;
  inIndex = 0;
  inVariance = 0;
  while (inIndex < inNumberTrees) {
    inVariance += (inSizes[inIndex] - inMeam) * (inSizes[inIndex] - inMeam);
    inIndex++;
  }
  inVariance /= (inNumberTrees - 1);
  free(inSizes);
  return sqrt (inVariance);
}

*/

Forest *Select (Forest **stForestsParam, int *stPopulationParam) {
  int boValid;
  int inIndex;
  int inValidateIndex;

  int inSelectedIndex;
  int inPosition;
  int *stSelected = Malloc(int, 3);
  Forest *stForest;

  inIndex = 0;
  inPosition = 0;
  while (inIndex < inPopSize && inPosition < 3) {
    stSelected[inPosition] = GetRamdomNumber(0, inPopSize);
    boValid = 1;
    inValidateIndex = 0;
    while (inValidateIndex < inPosition) {
      if (stSelected[inValidateIndex] ==  stSelected[inPosition])
        boValid = 0;
      inValidateIndex++;
    }
    if (boValid == 1) {
      inIndex++;
      inPosition++;
    }
  }

  inIndex = 0;
  inSelectedIndex = 0;
  while (inIndex < inPosition) {
    if(stForestsParam[stPopulationParam[stSelected[inSelectedIndex]]]->fpFitness > stForestsParam[stSelected[inIndex]]->fpFitness)
      inSelectedIndex = inIndex;
    inIndex++;
  }

  stForest = stForestsParam[stPopulationParam[stSelected[inSelectedIndex]]];
  free(stSelected);
  return stForest;
}

Forest *ApplyOperator1(Forest *stForestParam) {
  int boFound;
  float inDifference = 0;
  int inAdjacents;

  int inNumber;
  int inNumberNodes;
  int inIndex;
  int inIndexP;
  int inIndexA;
  int inIndexL;
  int inIndexRaiz;
  int inAdjacentTries;
  int inNodeTries;
  int inTree;
  int *stNodes;
  PositionColunm * stColunm;
  Tree *stTempTreeFrom;
  Tree *stTempTreeTo;
  Tree *stTree;
  Tree *stTreeAux;
  Tree *stTreeA;
  Tree *stTreeP;
  Forest *stForest;
  FILE *Stream;
 	
  //Sorteia os nodos: p e a
  inTree = 0;
//printf("inicio operador 1 \n");
//  stTempTreeFrom = GetTree(stForestParam, inTree);
//printf("depois de getTree operador 1 \n");
	//printf("operador 1 fitness %f  \n", stForestParam->fpFitness);
	//print_forest(stForestParam);

  inNumberNodes = stForestParam->stTrees[inTree]->inNumberNodes;
  inNodeTries = 0;
  boFound = 0;
  while (boFound == 0 && inNodeTries < TRIES) {
    inIndexP = GetRamdomNumber(1, inNumberNodes - 1);
    inIndexRaiz = inIndexP;
    while (inIndexRaiz > 0 && stForestParam->stTrees[0]->stDephs[inIndexRaiz] > stForestParam->stTrees[inTree]->stDephs[inIndexP] - 1) {
      inIndexRaiz--;
    }
    inIndexL = GetRange(stForestParam->stTrees[inTree], inIndexP);
    inAdjacents = GetNumberAdjacentNodes(stForestParam->stTrees[inTree]->stNodes[inIndexP]);
    stNodes = GetAdjacentNodes(stForestParam->stTrees[inTree]->stNodes[inIndexP]);
//	printf("node p %d inAdjacents %d    \n", stTempTreeFrom->stNodes[inIndexP], inAdjacents);
    inAdjacentTries = 0;
    while (boFound == 0 && inAdjacentTries < TRIES && inAdjacents > 1) {
      inIndexA = GetRamdomNumber(0, inAdjacents);
  //    printf("node A %d \n", stNodes[inIndexA]);
      stColunm = GetPosition(stNodes[inIndexA], stForestParam->inForestName);
	
      inIndexA = stColunm->inIndex;
        free(stColunm);
	//printf("inNodeA na arvore op1 %d op2 %d\n", stForestParam->stTrees[0]->stNodes[inIndexA], stTempTreeFrom->stNodes[inIndexA]);
      if ((inIndexA != inIndexRaiz) && (GetDegree(stForestParam->stTrees[inTree], inIndexA) < inRestriction) && (inIndexA < inIndexP || inIndexA > inIndexL)){
        boFound = 1;
        }
      inAdjacentTries++;
    }
    free(stNodes);	
    inNodeTries++;
  }

  if (boFound == 0){
    return  NULL;
    }

  inDifference -= GetWeight(stForestParam->stTrees[inTree]->stNodes[inIndexRaiz], stForestParam->stTrees[inTree]->stNodes[inIndexP]);
  inDifference += GetWeight(stForestParam->stTrees[inTree]->stNodes[inIndexA], stForestParam->stTrees[inTree]->stNodes[inIndexP]);

//printf("operador 1 inIndexP  %d inIndexA %d inIndexRaiz %d  \n",inIndexP, inIndexA, inIndexRaiz);
 
  //Aplica o operador1
  stTempTreeTo = CopySubTree(stForestParam->stTrees[inTree], inIndexP, inIndexL, stForestParam->stTrees[inTree]->stDephs[inIndexA]);
  stTreeAux = BuildTreeFrom(stForestParam->stTrees[inTree], inIndexP, inIndexL);
  if (inIndexA > inIndexP)
    inIndexA -= (inIndexL - inIndexP + 1);
  stTree = BuildTreeTo(stTreeAux, stTempTreeTo, inIndexA);

  //Cria a nova floresta
  inCurrentForestName++;
  inNumber = stForestParam->inNumberTrees;
  stForest = CreateForest(inNumber, inCurrentForestName);
  stForest->stTrees[0] = stTree;
  stForest->fpFitness = stForestParam->fpFitness + inDifference;

  //Atualiza a matriz de posicionamento
  if (inIndexP - 1 < inIndexA)
    inIndex = inIndexP - 1;
  else
    inIndex = inIndexA;
  while (inIndex < stTree->inNumberNodes) {
    AddPosition(stTree->stNodes[inIndex], inCurrentForestName, stTree->inTreeName, inIndex, stTree->stDephs[inIndex]);
    inIndex++;
  }
  SetGenitor(inCurrentForestName, stForestParam->inForestName);

 //	printf("operador 1 inIndexP  %d inIndexA %d fitness %f  \n",inIndexP, inIndexA, stForest->fpFitness);
//	print_forest(stForest);


  free(stTreeAux->stNodes);
  free(stTreeAux->stDephs);
  free(stTreeAux);
  free(stTempTreeTo->stNodes);
  free(stTempTreeTo->stDephs);
  free(stTempTreeTo);
  stTree = NULL;

  return stForest;
}

Forest *ApplyOperator2(Forest *stForestParam) {
  int boFound;
  float inDifference = 0;
  int inAdjacents;
  int inNumber;
  int inNumberNodes;
  int inIndex;
  int inIndexP;
  int inIndexA;
  int inIndexR;
  int inIndexL;
  int inIndexLR;
  int inIndexRaiz;
  int inAdjacentTries;
  int inNodeTries;
  int inTree;
  int *stNodes;
  PositionColunm * stColunm;
  Tree *stTree;
  Tree *stTreeAux;
  Tree *stTempTree1;
  Tree *stTempTree2;
  Forest *stForest;
  FILE *Stream;
 
   //printf("inicio operador 2 \n");
  //Sorteia os nodos: p, a e r
  inTree = 0;
 // stTempTreeFrom = GetTree(stForestParam, inTree);
//	printf("depois de gettree operador 2 \n");
//	printf("operador 2 fitness %f  \n", stForestParam->fpFitness);
//	print_forest(stForestParam);
  inNumberNodes = stForestParam->stTrees[inTree]->inNumberNodes;
  inNodeTries = 0;
  boFound = 0;
  while (boFound == 0 && inNodeTries < TRIES) {
    inIndexP = GetRamdomNumber(1, inNumberNodes - 1);
    inIndex = GetRange(stForestParam->stTrees[inTree], inIndexP);
    inIndexL = GetRange(stForestParam->stTrees[inTree], inIndexP);

	
    inIndexR = GetRamdomNumber(inIndexP, inIndexL - inIndexP);
    inIndexRaiz = inIndexP;
    while (inIndexRaiz > 0 && stForestParam->stTrees[0]->stDephs[inIndexRaiz] > stForestParam->stTrees[inTree]->stDephs[inIndexP] - 1) {
      inIndexRaiz--;
    }
    inAdjacents = GetNumberAdjacentNodes(stForestParam->stTrees[inTree]->stNodes[inIndexR]);
    stNodes = GetAdjacentNodes(stForestParam->stTrees[inTree]->stNodes[inIndexR]);
    inAdjacentTries = 0;
   //printf("inAdjacents %d      ", inAdjacents);	
//	printf("node r %d inAdjacents %d    \n", stTempTreeFrom->stNodes[inIndexR], inAdjacents);
    if(GetDegree(stForestParam->stTrees[inTree], inIndexR) < inRestriction)
    {	  
   	 while (boFound == 0 && inAdjacentTries < TRIES && inAdjacents > 1) {
      		inIndexA = GetRamdomNumber(0, inAdjacents);
		//printf("antes de getposition operador 2 \n");
		//printf("inIndexA %d \n", inIndexA);
      		stColunm = GetPosition(stNodes[inIndexA], stForestParam->inForestName);
		//printf("depois de getposition operador 2 \n");
      		inIndexA = stColunm->inIndex;
	        free(stColunm);
      		if ((inIndexA != inIndexRaiz) && (GetDegree(stForestParam->stTrees[inTree], inIndexA) < inRestriction) && (inIndexA < inIndexP || inIndexA > inIndexL))
        		boFound = 1;
      		inAdjacentTries++;
    	}
    	inNodeTries++;
     }	
	//else
	//	printf("R nao valido \n");
	free(stNodes);
  }

  if (boFound == 0)
    return NULL;

  inDifference -= GetWeight(stForestParam->stTrees[inTree]->stNodes[inIndexRaiz], stForestParam->stTrees[inTree]->stNodes[inIndexP]);
  inDifference += GetWeight(stForestParam->stTrees[inTree]->stNodes[inIndexA], stForestParam->stTrees[inTree]->stNodes[inIndexR]);

  //Aplica o operador2
  inIndexLR = GetRange(stForestParam->stTrees[inTree], inIndexR);
  stTempTree1 = CopySubTree(stForestParam->stTrees[inTree], inIndexR, inIndexLR, stForestParam->stTrees[inTree]->stDephs[inIndexA]);
  stTempTree2 = ModifySubTree(stForestParam->stTrees[inTree], inIndexP, inIndexL, inIndexR, stForestParam->stTrees[inTree]->stDephs[inIndexA]);
  stTreeAux = BuildTreeFrom(stForestParam->stTrees[inTree], inIndexP, inIndexL);
  if (inIndexA > inIndexP)
    inIndexA -= (inIndexL - inIndexP + 1);
  stTree = BuildModifiedTreeTo(stTreeAux, stTempTree1, stTempTree2, inIndexA);

  //Cria a nova floresta
  inCurrentForestName++;
  inNumber = stForestParam->inNumberTrees;
  stForest = CreateForest(inNumber, inCurrentForestName);
  stForest->stTrees[0] = stTree;
  stForest->fpFitness = stForestParam->fpFitness + inDifference;

  //Atualiza a matriz de posicionamento
  if (inIndexP - 1 < inIndexA)
    inIndex = inIndexP - 1;
  else
    inIndex = inIndexA;
  while (inIndex < stTree->inNumberNodes) {
    AddPosition(stTree->stNodes[inIndex], inCurrentForestName, stTree->inTreeName, inIndex, stTree->stDephs[inIndex]);
    inIndex++;
  }
  SetGenitor(inCurrentForestName, stForestParam->inForestName);

//printf("operador 2 inIndexP  %d inIndexA %d fitness %f  \n",inIndexP, inIndexA, stForest->fpFitness);
//	print_forest(stForest);

  free(stTreeAux->stNodes);
  free(stTreeAux->stDephs);
  free(stTreeAux);
  free(stTempTree1->stNodes);
  free(stTempTree1->stDephs);
  free(stTempTree1);
  free(stTempTree2->stNodes);
  free(stTempTree2->stDephs);
  free(stTempTree2);
  stTree = NULL;

  return stForest;
}

void CalculateStatistics (Forest **stForestsParam, int *stPopulationParam, float *stStatisticsParam) {
	int inForest;
	double fpMeam;
	
	fpMeam = 0;
	
	inForest = 0;
	while (inForest < inPopSize) {
	  fpMeam +=   stForestsParam[stPopulationParam[inForest]]->fpFitness;
	  inForest++;
	}
	fpMeam /= inPopSize;
	stStatisticsParam[0] = fpBestFitness;
	stStatisticsParam[1] = fpMeam;
	stStatisticsParam[2] = fpWorstFitness;
}


int InsertPop (Forest **stForestsParam, int *stPopulationParam, Forest *stForestParam) {
  int inIndex;

  stForestsParam[inComSize] = stForestParam;

  if (inPopSize > 0)
  {
    inIndex = inPopSize;
    while (inIndex > 0 && stForestsParam[stPopulationParam[inIndex - 1]]->fpFitness > stForestParam->fpFitness)
    {
      //printf("inIndex %d \n",inIndex);
      stPopulationParam[inIndex]  = stPopulationParam[inIndex - 1];
      inIndex--;
    }
  }
  else
  {
    inIndex = inPopSize;
  }

  if (inPopSize < inMaxPop)
    inPopSize++;

  if (inIndex < inMaxPop)
	stPopulationParam[inIndex] = inComSize;

  if (fpBestFitness > stForestParam->fpFitness)
    fpBestFitness =  stForestParam->fpFitness;

  //if (fpWorstFitness < stForestsParam[stPopulationParam[inPopSize - 1]]->fpFitness)
  fpWorstFitness = stForestsParam[stPopulationParam[inPopSize - 1]]->fpFitness;

  inComSize++;
}


int BinarySearch (int *stRootParam, int inSearchParam, int inLastParam) {
  int inFirst = 0;
  int inMidle = (inFirst + inLastParam) / 2;
  while ((inFirst <= inLastParam) && (stRootParam[inMidle]!= inSearchParam)){
    if(stRootParam[inMidle] > inSearchParam){
      inLastParam = inMidle - 1;
    }//Busca na parte superior
    else
    if(stRootParam[inMidle] < inSearchParam){
       inFirst = inMidle + 1;
    }//Busca na parte inferior
    inMidle = (inFirst + inLastParam) / 2;
  }
  if(stRootParam[inMidle] == inSearchParam)
    return inMidle; //encontrou, retorna a posi��o
  else
    return -1;  //n�o encontrou, retorna um aviso
}

//---------------------------------------------------------------------------
void LoadPopulation(Forest **stForestsParam, int *stPopulationParam, int inPopulationSizeParam, int inRestrictionParam, char *FileNameParam) 
{
  int inForest;
  int inIndex;
  int inDegree;
  int inNode;
  int indice;
  int inStart = 0;
  Tree *stTree;
  Forest *stForest;
    int pos;
  //read_graph(&g, FileNameParam, FALSE);
//  printf("inicio loadpopulation \n");
  inFirstForest = 1;
  inCurrentForestName = 0;
   inStart = 0;//GetRamdomNumber(0,g.nvertices);
//	printf("depois de star %d \n", inStart);
//	printf("inCurrentForestName %d  inPopulationSize %d \n", inCurrentForestName, inPopulationSizeParam);
  while (inCurrentForestName < inPopulationSizeParam) 
 {
// 	printf("iniciando individuos %d\n",inCurrentForestName);
    inNode = 0;
	
    while (inNode <= g.nvertices) {
      	inDegree = 0;
    	tree1[inNode].inNumberAdjacents = 0;
	tree1[inNode].flag = false;
      	while (inDegree < g.degree[inNode]) {
        	g.edges[inNode][inDegree].weight  = GetRamdomNumber(1, g.nvertices);
     		inDegree++;
      	}
      	inNode++;
    }
	//print_graph(&g);
//     inStart = GetRamdomNumber(0,g.nvertices);
//    // if (inCurrentForestName > 0)
//     {
//         pos = BinarySearch (stRoot, inStart, inCurrentForestName);
// 	while (pos != (-1))
// 	{  // printf("raiz repetida \n");
// 	    inStart = GetRamdomNumber(0,g.nvertices);
// 	     pos = BinarySearch (stRoot, inStart, inCurrentForestName);	
// 	}
//     }
//     stRoot[inCurrentForestName] = inStart;	
//      printf("inStart %d\n",inStart);
    stTree = Prim(&g, inStart, inRestrictionParam);
  //  printf("incurrentforestnoame %d\n",inCurrentForestName);
    inCurrentForestName++;
    stForest = CreateForest(1, inCurrentForestName);
    stForest->stTrees[0] = stTree;

    //Atualiza a matriz de posicionamento
    inIndex = 0;
    while (inIndex < stTree->inNumberNodes) 
    {
      AddPosition(stTree->stNodes[inIndex], inCurrentForestName, stTree->inTreeName, inIndex, stTree->stDephs[inIndex]);
	//printf(" %d ",stTree->stDephs[inIndex]);
      inIndex++;
    }
    //printf("\n");
    SetGenitor(inCurrentForestName, inCurrentForestName);

    stForest->fpFitness = InitFitness(stForest);	
//	printf("fitness %f \n", stForest->fpFitness);
// 	print_forest(stForest);
    InsertPop(stForestsParam, stPopulationParam, stForest);
    stForest = NULL;
    inForest++;
	
  }
//  free(stRoot);
}

//******************* imprime uma floresta ***************//
void print_forest( Forest * stForest) {
    int i;
    //printf("print-forest inNumberTrees %d\n", stForest->inNumberTrees);
    for( i = 0; i < stForest->inNumberTrees; i++ ) {
        print_tree( stForest->stTrees[ i ], "Arvore", 0, 0 );
    }
}

//********** imprime uma arvore ****************//

void print_tree( Tree *stTreeParam, char *chParam, int inStart, int inEnd ) {
    int i;
    printf( "\n" );
    printf( "-- %s -- %d -- %d", chParam, stTreeParam->inTreeName, stTreeParam->inNumberNodes);
    printf( "\n" );
//     
    printf( "Node:" );
    for( i = 0; i < stTreeParam->inNumberNodes; i++ ) {
        printf( "%2i,", stTreeParam->stNodes [i] );
    }
    printf("\n" );
    
    printf( "Deph:" );
    for( i = 0; i < stTreeParam->inNumberNodes; i++ ) {
        printf( "%2i,", stTreeParam->stDephs [ i ] );
    }
    printf( "\n" );
    
  //  printf( "Degree:" );
  //  for( i = 0; i < stTreeParam->inNumberNodes; i++ ) {
   //     printf( "%2i,", stTreeParam->stDegrees [ i ] );
    //}
    //printf("\n" );
}



void EARun(int inNumberGenerationsParam, int inNumberPopulationParam, int inRestrictionParam, int NumExecParam) {
  Forest **stForests;
  Forest *stForest;
  Forest *stNewForest;
  int *stPopulation = Malloc(int, (inNumberPopulationParam+1));
  float **stStatistics = Malloc(float*, inNumberGenerationsParam);
  unsigned int seed;
  //printf("Depois de aloca��es...\n");
  int inIndex;
  int inTree;
  double fpOperator;
  clock_t  inicio, fim;
  clock_t  inicioAE, fimAE;	
  double difference, differenceAE;
  char  ResultArq2[100];
  FILE *Stream2;
  char straux[6];
  FILE *Stream;
  char  ResultArq[100];
  //srand(time(NULL)); 
  inicioAE = clock();	
  seed = time(NULL);	
  	
  int i;	
  strcpy(ResultArq2,"NDE");
  strcat( ResultArq2, "_pop" );
  sprintf(straux,"%d", inNumberPopulationParam);
  strcat( ResultArq2, straux);
  strcat( ResultArq2,"_ge" );
  sprintf(straux,"%d", inNumberGenerationsParam);
  strcat( ResultArq2, straux);
  strcat( ResultArq2,"_restriction" );
  sprintf(straux,"%d_", inRestrictionParam);
  strcat( ResultArq2, straux);
  strcat( ResultArq2, GraphArq);
  Stream2 = fopen(ResultArq2, "w");	
  inRestriction = inRestrictionParam;	
  inicio = clock();
  LoadAdjacentTable();
  fim = clock();
  difference = double(fim-inicio)/CLOCK_TICKS_PER_SECOND;
  printf("tempo loadadjacenttable %f\n",difference); 		
  inMaxCom = inNumberGenerationsParam;
  inMaxPop = inNumberPopulationParam;
  inMaxColunm = (int)ceil(sqrt(inNumberNodesAT)*30 + inMaxPop); 	
 printf("inMaxColunm %d \n", inMaxColunm);
//   inMaxColunm = inMaxCom + 3*inMaxPop;	
  		
//printf("Depois de Load_adjacent...\n");
  LoadPositionMatrix(stNodesAT);
  stForests = Malloc(Forest*, inMaxColunm);
  printf("Depois de Load_position...\n");
  int cont = 0;
   for (int numExec = 1; numExec <= NumExecParam; numExec++)
    {
	srand(seed);
// 	printf("seed %d\n", seed);
	 /* specifying to use Mersenne twister MT-19937 as the uniform PRNG */
  	strcpy(ResultArq,"NDE");
        strcat( ResultArq, "_pop" );
	sprintf(straux,"%d", inNumberPopulationParam);
        strcat( ResultArq, straux);
        strcat( ResultArq,"_ge" );
        sprintf(straux,"%d", inNumberGenerationsParam);
	strcat( ResultArq, straux);
        strcat( ResultArq,"_restriction" );
        sprintf(straux,"%d", inRestrictionParam);
	strcat( ResultArq, straux);
	strcat( ResultArq,"_exec" );
        sprintf(straux,"%d_", numExec);
	strcat( ResultArq, straux);
	strcat( ResultArq, GraphArq);
	Stream = fopen(ResultArq, "w");
  	for( i=0; i<inNumberNodesAT; i++)
        {
  	    	PI[i].inNumberColunms = 0;
        }
	for(i=0; i<inMaxColunm; i++) {
        	pi[i] = -1;
   	}
	//Carrega a populacao inicial
  	inBestForest = 1;
  	inWorstForest = 1;
  	fpBestFitness = 20000000;
  	fpWorstFitness = 0;
  	
  	inComSize = 0;
  	inPopSize = 0;
  	inicio = clock();
// 	printf("antes de loadPopulation \n");
	LoadPopulation (stForests, stPopulation, inMaxPop, inRestrictionParam,GraphArq);
  	//print_forest( stForests[stPopulation[0]]);
	//	printf("Depois de Load_population... \n");
 
  	//Entra no ciclo de evolucao da populacao
  	inGeneration = 1;
  	
  	while (inGeneration <= inMaxCom) {
    		stStatistics[inGeneration - 1] = Malloc(float, 3);
    		stForest = Select (stForests, stPopulation);
    		fpOperator = GetRamdomNumber(1,3);
   		// printf("ingeneration %d\n",inGeneration);
    		if (fpOperator == 1) {
			//	printf("aplicacao do operador 1 \n");
      			stNewForest = ApplyOperator1 (stForest);
    		}
    		else //if (fpOperator == 2) 
   		{
			//	printf("aplicacao do operador 2 \n");
      			stNewForest = ApplyOperator2 (stForest);
   		 }
    		//else
    		//{
			//printf("aplicacao do operador 3 \n"); 
       			//stNewForest = ApplyOperator3 (stForest);
    		//}
    		if (stNewForest != NULL) {
      			InsertPop (stForests, stPopulation, stNewForest);
    		
			CalculateStatistics (stForests, stPopulation, stStatistics[inGeneration - 1]);
			if (reloadPi == true)
			{
				stForests = reLoadPositionMatrix(stForests, inMaxPop, stPopulation);
				reloadPi = false;
				//printf("entrei em reloadPi inGeneration %d \n", inGeneration);
				//for (int y=0; y < PopSize; y++)
				//	printf("inforestName %d \n", stForests[y]->inForestName);
			}
    			inGeneration ++;
		}
  	}
  	fim = clock();
  	difference = double(fim-inicio)/CLOCK_TICKS_PER_SECOND;
  	fprintf(Stream2, " %4i %5.3f %5.3f %3.5f\n", numExec,stStatistics[inGeneration-2][0],stStatistics[inGeneration-2][1],difference);
 	// print_forest( stForests[stPopulation[0]]);
  	inGeneration = 0;
   	while (inGeneration < inMaxCom) 
	{
      		fprintf(Stream, "%i %f %f %f \n", inGeneration, stStatistics[inGeneration][0], stStatistics[inGeneration][1], stStatistics[inGeneration][2]);
		free(stStatistics[inGeneration]);
      		inGeneration++;
    	}
	fclose(Stream);
	printf("Execucao %d\n", numExec);
	seed+=rand()/MAXINT;
	 inIndex = 0;
//   	printf("inComSize %d \n", inComSize);
  	while (inIndex < inComSize) {
    		ReleaseForest(stForests[inIndex]);
    		free(stForests[inIndex]);	
    		inIndex++;
  	}
  }	
  ReleasePositionMatrix();

//   inIndex = 0;
//   printf("inComSize %d \n", inComSize);
//   while (inIndex < inComSize) {
//     ReleaseForest(stForests[inIndex]);
//     free(stForests[inIndex]);	
//     inIndex++;
//   }
  free(pi);
  free(stForests);
  free(stPopulation);
  free(stStatistics);
	fimAE = clock();
differenceAE = double(fimAE-inicioAE)/CLOCK_TICKS_PER_SECOND;
printf("tempo total ae %f\n",differenceAE);
}

